package com.sunsharing.dispatch.graph;

import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;
import java.util.concurrent.LinkedBlockingDeque;

/**
 * Created with IntelliJ IDEA.
 * User: criss
 * Date: 13-4-13
 * Time: 下午5:30
 * To change this template use File | Settings | File Templates.
 */
public class AF {

    boolean isAF = true;
    Graph graph;
    int n;
    int start,end;
    Stack<Integer> theStatck;

    private ArrayList<Integer> tempList;
    private String counterexample;

    public AF(Graph graph,String start,String end)
    {
        this.graph = graph;
        this.start = graph.getIndexByNodeId(start);
        this.end = graph.getIndexByNodeId(end);
    }

    public List<List<String>> getResult()
    {
        List<Stack<Integer>> stacks = new ArrayList<Stack<Integer>>();
        graph.printGraph();
        n = graph.getN();
        theStatck = new Stack<Integer>();

        if(!isConnectable(start,end))
        {
            isAF = false;
            counterexample = "节点之间没有通路";
        } else
        {
            for(int j=0;j<n;j++)
            {
                tempList = new ArrayList<Integer>();
                for(int i=0;i<n;i++)
                {
                    tempList.add(0);
                }
                graph.getVertexList()[j].setAllVisitedList(tempList);
            }

            isAF = af(start,end,stacks);

        }

        //return isAF;
        List<List<String>> result = new ArrayList<List<String>>();
        for(Stack<Integer> s:stacks)
        {
            List<String> nodes = new ArrayList<String>();
            while(!s.empty())
            {
                nodes.add(graph.displayVertex(s.pop()));
            }

            result.add(nodes);
        }
        return result;
    }

    private boolean af(int start, int end,List<Stack<Integer>> stacks) {
        graph.getVertexList()[start].setWasVisited(true); // mark it
        theStatck.push(start); // push it

        while (!theStatck.isEmpty()) {
            int v = getAdjUnvisitedVertex(theStatck.peek());
            if (v == -1) // if no such vertex,
            {
                tempList = new ArrayList<Integer>();
                for (int j = 0; j < n; j++) {
                    tempList.add(0);
                }
                graph.getVertexList()[theStatck.peek()]
                        .setAllVisitedList(tempList);// 把栈顶节点访问过的节点链表清空
                theStatck.pop();
            } else // if it exists,
            {
                theStatck.push(v); // push it
            }

            if (!theStatck.isEmpty() && end == theStatck.peek()) {
                graph.getVertexList()[end].setWasVisited(false); // mark it
                //printTheStack(theStatck);
                stacks.add((Stack)theStatck.clone());
                //System.out.println();
                theStatck.pop();
            }
        }

        return isAF;
    }

    //判断两个节点是否能够联通
    private boolean isConnectable(int start,int end)
    {
        ArrayList<Integer> queue = new ArrayList<Integer>();
        ArrayList<Integer> visited = new ArrayList<Integer>();
        queue.add(start);

        while(!queue.isEmpty())
        {
            for(int j=0; j<n;j++)
            {
                if (graph.getAdjMat()[start][j] == 1 && !visited.contains(j)) {
                    queue.add(j);
                }
            }
            if(queue.contains(end))
            {
                return true;
            } else {
                visited.add(queue.get(0));
                queue.remove(0);
                if(!queue.isEmpty())
                {
                    start = queue.get(0);
                }
            }
        }
        return false;
    }

    public String counterexample(){
        for(Integer integer:theStatck)
        {
            counterexample += graph.displayVertex(integer);
            if(integer != theStatck.peek())
            {
                counterexample += "-->";
            }
        }
        return counterexample;
    }

    // 与节点v相邻，并且这个节点没有被访问到，并且这个节点不在栈中
    public int getAdjUnvisitedVertex(int v) {
        ArrayList<Integer> arrayList = graph.getVertexList()[v]
                .getAllVisitedList();
        for (int j = 0; j < n; j++) {
            if (graph.getAdjMat()[v][j] == 1 && arrayList.get(j) == 0
                    && !theStatck.contains(j)) {
                graph.getVertexList()[v].setVisited(j);
                return j;
            }
        }
        return -1;
    }

    public void printTheStack(Stack<Integer> theStack2) {
//        for (Integer integer : theStack2) {
//            System.out.print(graph.displayVertex(integer));
//            if (integer != theStack2.peek()) {
//                System.out.print("-->");
//            }
//        }
    }

}
